/**
 * Created by L.jp
 * Description:输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
 * （注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
 * User: 86189
 * Date: 2022-01-14
 * Time: 22:14
 */
 class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
     public static int getLength(ListNode list){
         if(list == null){
             return 0;
         }
         int len=0;
         while(list!=null){
             len++;
             list=list.next;
         }
         return len;
     }
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
         if(pHead1==null || pHead2 == null){
             return null;
         }
         //分别求得两个链表的长度
        int len1=getLength(pHead1);
        int len2=getLength(pHead2);
        //不知道谁长谁短，那么就利用绝对值求法来求出相差的节点数也就是步数，让长的先走step步,然后再一起走，直到相遇时就是第一个公共节点
        int step=Math.abs(len1-len2);
        //如果第一个链表长
        if(len1>len2){
            //那么phead1需要先走step步
            while(step>0){
                pHead1=pHead1.next;
                step--;
            }
        }else{
            //phead2先走step步
            while(step > 0){
                pHead2 = pHead2.next;
                step--;
            }
        }
        //走完了，然后一起走
        while(pHead1!=null &&  pHead2 != null){
            //相等时求得公共节点
            if(pHead1==pHead2){
                return pHead1;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return null;
    }

}
